On the existence of radial Moore graphs for every radius and every degree

Title: On the existence of radial Moore graphs for every radius and every degree
Creator: Gómez, José; Miller, Mirka
Relation: European Journal of Combinatorics Vol. 47, Issue July 2015, p. 15-22
Publisher Link: http://dx.doi.org/10.1016/j.ejc.2015.01.004
Publisher: Academic Press
Resource Type: journal article
Date: 2015
Description: The degree/diameter problem is to determine the largest graphs of given maximum degree and given diameter. General upper bounds-called Moore bounds-for the order of such graphs are attainable only for certain special graphs, called Moore graphs. Moore graphs are scarce and so the next challenge is to find graphs which are somehow "close" to the nonexistent ideal of a Moore graph by holding fixed two of the parameters, order, diameter and maximum degree, and optimising the third parameter. In this paper we consider the existence of graphs that have order equal to Moore bound for given radius and maximum degree and as the relaxation we require the diameter to be at most one more than the radius. Such graphs are called radial Moore graphs. In this paper we prove that radial Moore graphs exist for every diameter and every sufficiently large degree, depending on the diameter.
Subject: radial Moore graphs; radius; degree; diameter
Identifier: http://hdl.handle.net/1959.13/1335973
Identifier: uon:27524
Identifier: ISSN:0195-6698
Language: eng
Reviewed

		Thumbnail	File	Description	Size	Format